
# 全排列

def permute(nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    result = []
    temp = []

    def backtrack(used):
        if len(temp) == len(nums) and temp not in result:
            result.append(temp[:])
            return

        for i in range(0, len(nums)):
            if nums[i] not in used:
                temp.append(nums[i])
                used.append(nums[i])
                backtrack(used)
                temp.pop()
                used.remove(nums[i])

    used = []
    backtrack(used)
    return result


if __name__ == "__main__":
    permute([1,2,3])